package com.ywk.base.dataStructure.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

//堆排序（升序）
public class HeapSort {

	public static void main(String[] args) {
		int[] arr= {81,49,19,38,97,76,13,19};
		/*int[] arr = new int[8000000];
		for (int i = 0; i < arr.length; i++) {
			arr[i]=(int)(Math.random()*80000);
		}*/
		Date d1=new Date();
		SimpleDateFormat s=new SimpleDateFormat("yyyy-MM-dd hh:mm:ss");
		System.out.println("排序前的时间："+s.format(d1));
		heapSort(arr);
		Date d2=new Date();
		System.out.println("排序后的时间："+s.format(d2));
	}
	//
	public static void heapSort(int[] arr) {
		for (int i = arr.length/2-1; i >=0 ; i--) {
			sift(arr, i, arr.length-1);
		}
		for (int j = arr.length-1; j > 0; j--) {
			int temp=arr[0];
			arr[0]=arr[j];
			arr[j]=temp;
			sift(arr, 0, j-1);
		}
		System.out.println(Arrays.toString(arr));
	}
	
	public static void sift(int[] arr,int parent,int end) {
		int temp=arr[parent];
		int child=2*parent+1;
		while(child<=end) {
			if(child+1<end&&arr[child]<arr[child+1]) {
				child++;
			}
			if(arr[child]>temp) {
				arr[parent]=arr[child];
				parent=child;
				child=2*parent+1;
			}else {
				break;
			}
		}
		arr[parent]=temp;//最大值放到后面
	}
}
